Random_Discrete_Morse

Computing the topological type, or homology, of a given a simplicial complex is straight forward, but not always computationally feasible. The bottleneck is in computing the Smith Normal Form, which is a polynomial time algorithm [Kannan-Bachem], but still too slow on large examples (about cubic).

Discrete Morse theory [Whitehead, Forman] provides a tool set which can be used to find reasonable upper bounds.  A randomized search for small discrete Morse vectors was introduced by Benedetti and Lutz, which we implemented as a client for the topological software package polymake.

I gave a workshop on Random_Discrete_Morse at the Homology: Theoretical and Computational Aspects (HTCA 2015) conference in Genoa, Italy.

While experimenting with Random_Discrete_Morse, we discovered a whole family of contractible, yet non-collapsible simplicial 2-complexes. We call them the sawblade complexes. Read more about the sawblade complexes here.

This project was joint work with Frank Lutz and Michael Joswig, with help from Benjamin Lorenz, Bruno Benedetti, and Karim Adiprasito.

References